package leetcode_401_500;

import java.util.*;

public class LeeCode_417 {
    public static void main(String[] args) {
//        System.out.println(pacificAtlantic(new int[][]{{1, 2, 2, 3, 5}, {3, 2, 3, 4, 4}, {2, 4, 5, 3, 1}, {6, 7, 1, 4, 5}, {5, 1, 1, 2, 4}}));
//        System.out.println(pacificAtlantic(new int[][]{{10, 10, 10}, {10, 1, 10}, {10, 10, 10}}));
        System.out.println(pacificAtlantic(new int[][]{{1,2,3}, {8,9,4}, {7,6,5}}));
    }
    private static List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        boolean[][] dp1 = new boolean[m][n];
        Arrays.fill(dp1[0], true);
        for (int i = 0; i < m; i++) {
            dp1[i][0] = true;
        }
        Set<String> used1 = new HashSet<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!used1.contains(i + "," + j) && dp1[i][j]){
                    dfs(dp1, heights, used1, i, j);
                }
            }
        }

        boolean[][] dp2 = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            dp2[i][n - 1] = true;
        }
        Arrays.fill(dp2[m - 1], true);
        Set<String> used2 = new HashSet<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!used2.contains(i + "," + j) && dp2[i][j]){
                    dfs(dp2, heights, used2, i, j);
                }
            }
        }

        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp1[i][j] && dp2[i][j]){
                    List<Integer> list = new ArrayList<>();
                    list.add(i);
                    list.add(j);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
    private static void dfs(boolean[][] dp, int[][] heights, Set<String> used, int i, int j){
        int m = heights.length, n = heights[0].length;
        String key = i + "," + j;
        if (used.contains(key)){
            return;
        }
        used.add(key);
        if (i - 1 >= 0 && !dp[i - 1][j] && heights[i - 1][j] >= heights[i][j]){
            dp[i - 1][j] = true;
            dfs(dp, heights, used, i - 1, j);
        }
        if (i + 1 < m && !dp[i + 1][j] && heights[i + 1][j] >= heights[i][j]){
            dp[i + 1][j] = true;
            dfs(dp, heights, used, i + 1, j);
        }
        if (j - 1 >= 0 && !dp[i][j - 1] && heights[i][j - 1] >= heights[i][j]){
            dp[i][j - 1] = true;
            dfs(dp, heights, used, i, j - 1);
        }
        if (j + 1 < n && !dp[i][j + 1] && heights[i][j + 1] >= heights[i][j]){
            dp[i][j + 1] = true;
            dfs(dp, heights, used, i, j + 1);
        }
    }
}
